#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/7/15 21:11
# @USER    : Shengji He
# @File    : UniqueBinarySearchTrees.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:


class Solution(object):
    def numTrees(self, n):
        """
        Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?

        Example:
            Input: 3

            Output: 5

            Explanation:
                Given n = 3, there are a total of 5 unique BST's:

           1         3     3      2      1
            \       /     /      / \      \
             3     2     1      1   3      2
            /     /       \                 \
           2     1         2                 3

        :type n: int
        :rtype: int
        """
        C = 1
        for i in range(0, n):
            C = C * 2*(2*i+1)/(i+2)
        return int(C)


if __name__ == '__main__':
    print('done')
